package mysgoog.board;

/**
 * Class that keeps track of all board data, history, and organization of stones.
 * @author paul
 */
import java.util.*;
import mysgoog.gtp.*;
import mysgoog.util.*;

public class Board
{
    public Board(int len)
    {
        BOARD_LENGTH = len;
        BOARD_ELEMNUM = len * len;
        board = new Color[BOARD_ELEMNUM];
        for (int cnt = 0; cnt < BOARD_ELEMNUM; cnt++)
            board[cnt] = Color.EMPTY;
        wormAt = new Worm[BOARD_ELEMNUM];
        for (int cnt = 0; cnt < BOARD_ELEMNUM; cnt++)
            wormAt[cnt] = null;
    }

    public final int BOARD_LENGTH;
    public final int BOARD_ELEMNUM;
    protected Color[] board;
    protected LinkedList<HistoryEvent> history = new LinkedList<HistoryEvent>();
    protected LinkedList<Worm> white_worms = new LinkedList<Worm>(),
            black_worms = new LinkedList<Worm>();
    protected Worm[] wormAt;
    protected int turn = 0;
    protected int tsn = 0;

    public Board copy()
    {
        Lib.assertNotReached();
        // TODO
        Board res;
        res = new Board(BOARD_LENGTH);
        res.board = board.clone();
        res.history = new LinkedList<HistoryEvent>(history);
        res.white_worms = new LinkedList<Worm>(white_worms);
        res.black_worms = new LinkedList<Worm>(black_worms);
        res.wormAt = wormAt.clone();
        res.turn = turn;
        res.tsn = tsn;
        return res;
    }
    protected void addWorm(Color c, Worm worm)
    {
        getWorms(c).add(worm);
        for (Integer pos : worm)
            wormAt[pos] = worm;
    }
    protected void removeWorm(Color c, Worm worm)
    {
        getWorms(c).remove(worm);
        for (Integer pos : worm)
            wormAt[pos] = null;
    }
    public Color getStone(int pos)
    {
        return board[pos];
    }
    public int getStoneLibs(int pos)
    {
        Lib.assertTrue(inBoard(pos));
        int res = 0;
        for (int i : getAdjacent(pos))
            if (board[i] == Color.EMPTY)
                res++;
        return res;
    }
    public Worm wormAt(int pos)
    {
        return wormAt[pos];
    }
    public Collection<Worm> getWorms(Color color)
    {
        if (color == Color.BLACK)
            return black_worms;
        else
            return white_worms;
    }
    // TODO may do some buffer for mem
    public Set<Worm> calcCaptureWorms(Color c, int pos)
    {
        Lib.assertTrue(board[pos] == Color.EMPTY);
        HashSet<Worm> res = new HashSet<Worm>();
        for (Worm worm : getWorms(c.complement()))
        {
            ArrayList<Integer> adjs = getAdjacent(pos, worm);
            if (worm.getLibs().size() == 1 && adjs.size() > 0)
                res.add(worm);
        }
        return res;
    }
    public PosSet calcCaptures(Color c, int pos)
    {
        PosSet res = new PosSet();
        Set<Worm> worms = calcCaptureWorms(c, pos);
        for (Worm worm : worms)
            for (Integer i : worm)
                res.add(i);
        return res;
    }
    public synchronized boolean isLegal(Color c, int pos)
    {
        if (!inBoard(pos) || c == null || c == Color.EMPTY)
            return false;
        if (this.getStone(pos).isFilled())
            return false;
        // check forbidden moves
        if (history.size() > 0)
        {
            HistoryEvent he = history.getLast();
            if (he.player == c.complement() && he.captures.size() == 1 && he.captures.contains(pos))
            {
                PosSet caps = calcCaptures(c, pos);
                if (caps.size() == 1 && caps.contains(he.pos))
                    return false;
            }
        }
        // check suicide
        if (getStoneLibs(pos) == 0 && calcCaptures(c, pos).size() == 0)
        {
            HashSet<Worm> cnct = new HashSet<Worm>();
            for (Integer i : this.getAdjacent(pos))
            {
                if (board[i] == c)
                    cnct.add(wormAt(i));
            }
            boolean ok = false;
            for (Worm worm : cnct)
                if (worm.getLibs().size() > 1)
                    ok = true;
            if (!ok)
                return false;
        }
        return true;
    }
    public synchronized void play(Color c, int pos)
    {
        if (!isLegal(c, pos))
            throw new Error("IllegalMove " + new Vertex(posX(pos), posY(pos)));
        // check ko
        Set<Worm> capWorms = calcCaptureWorms(c, pos);
        // check cnct
        HashSet<Worm> cnct = new HashSet<Worm>();
        for (Integer i : this.getAdjacent(pos))
        {
            if (board[i] == c)
                cnct.add(wormAt(i));
        }
        // update history
        history.add(new HistoryEvent(turn, c, pos, capWorms, cnct));
        // update worms
        for (Worm worm : capWorms)
            removeWorm(c.complement(), worm);
        for (Worm worm : cnct)
            removeWorm(c, worm);
        Worm newWorm = new Worm(this, c);
        for (Worm worm : cnct)
            newWorm.addAll(worm);
        newWorm.add(pos);
        addWorm(c, newWorm);
        // update board
        for (Integer i : history.getLast().captures)
            board[i] = Color.EMPTY;
        board[pos] = c;
        turn++;
        tsn++;
    }
    public void pass(Color c)
    {
        history.addLast(new HistoryEvent(turn, c, -1, new HashSet<Worm>(), new HashSet<Worm>()));
        turn++;
    }
    public void undo()
    {
        HistoryEvent he = history.removeLast();
        if (he.pos != -1)
        {
            removeWorm(he.player, wormAt(he.pos));
            for (Worm worm : he.cnctWorms)
                addWorm(he.player, worm);
            for (Worm worm : he.captureWorms)
                addWorm(he.player.complement(), worm);
            board[he.pos] = Color.EMPTY;
            for (int i : he.captures)
                board[i] = he.player.complement();
        }
        turn--;
        tsn++;
    }
    public int getTurn()
    {
        return turn;
    }
    public int getTSN()
    {
        return tsn;
    }
    public LinkedList<HistoryEvent> getHistory()
    {
        return history;
    }
    @Override
    public String toString()
    {
        String letters = "   ";
        for (char c = 'A'; c < 'A' + BOARD_LENGTH; c++)
            if (c >= 'I')
                letters += (char) (c + 1);
            else
                letters += c;
        String res = "";
        res += letters + "\n";
        for (int y = BOARD_LENGTH - 1; y >= 0; y--)
        {
            res += Lib.fixLenInt(y + 1, 2) + " ";
            for (int x = 0; x < BOARD_LENGTH; x++)
            {
                int pos = makePos(x, y);
                if (board[pos] == Color.BLACK)
                    res += "O";
                else if (board[pos] == Color.WHITE)
                    res += "X";
                else if (board[pos] == Color.EMPTY)
                    res += "_";
                else
                    Lib.assertNotReached();
            }
            res += " " + Lib.fixLenInt(y + 1, 2);
            res += "\n";
        }
        res += letters + "\n";
        return res;
    }
    /**
     * [0..12]*[0..12] --> [0..168]
     * 
     * @param x
     * @param y
     * @return integer position for one-dimensional array
     */
    public int makePos(int x, int y)
    {
        if (x < 0 || x >= BOARD_LENGTH)
            return -1;
        if (y < 0 || y >= BOARD_LENGTH)
            return -1;
        return x + BOARD_LENGTH * y;
    }
    public int posX(int pos)
    {
        return pos % BOARD_LENGTH;
    }
    public int posY(int pos)
    {
        return pos / BOARD_LENGTH;
    }
    public boolean isNorthEdge(int pos)
    {
        return pos >= BOARD_LENGTH * (BOARD_LENGTH - 1);
    }
    public boolean isSouthEdge(int pos)
    {
        return pos < BOARD_LENGTH;
    }
    public boolean isWestEdge(int pos)
    {
        return pos % BOARD_LENGTH == 0;
    }
    public boolean isEastEdge(int pos)
    {
        return pos % BOARD_LENGTH == BOARD_LENGTH - 1;
    }
    public boolean isEdge(int pos)
    {
        return isWestEdge(pos) || isEastEdge(pos) || isNorthEdge(pos) || isSouthEdge(pos);
    }
    public int disToEdge(int pos)
    {
        // TODO to check
        int x = posX(pos);
        int y = posY(pos);
        int res = Math.min(x, y);
        res = Math.min(res, BOARD_LENGTH - 1 - x);
        res = Math.min(res, BOARD_LENGTH - 1 - y);
        return res;
    }
    public boolean isCorner(int p)
    {
        return p == 0 || p == BOARD_LENGTH - 1 || p == BOARD_LENGTH * (BOARD_LENGTH - 1)
                || p == BOARD_LENGTH * BOARD_LENGTH - 1;
    }
    public int north(int pos)
    {
        if (!inBoard(pos) || isNorthEdge(pos))
            return -1;
        return pos + BOARD_LENGTH;
    }
    public int south(int pos)
    {
        if (!inBoard(pos) || isSouthEdge(pos))
            return -1;
        return pos - BOARD_LENGTH;
    }
    public int west(int pos)
    {
        if (!inBoard(pos) || isWestEdge(pos))
            return -1;
        return pos - 1;
    }
    public int east(int pos)
    {
        if (!inBoard(pos) || isEastEdge(pos))
            return -1;
        return pos + 1;
    }
    public boolean inBoard(int p)
    {
        return p >= 0 && p <= BOARD_ELEMNUM - 1;
    }

    public boolean isAdjacent(int p1, int p2)
    {
        if (p1 > p2)
        {
            int tmp = p1;
            p1 = p2;
            p2 = tmp;
        }
        if (p2 - p1 == BOARD_LENGTH)
            return true;
        if (p2 - p1 == 1 && !isEastEdge(p1))
            return true;
        return false;
    }
    public ArrayList<Integer> getAdjacent(int pos)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (!isNorthEdge(pos))
            res.add(north(pos));
        if (!isSouthEdge(pos))
            res.add(south(pos));
        if (!isWestEdge(pos))
            res.add(west(pos));
        if (!isEastEdge(pos))
            res.add(east(pos));
        return res;
    }
    public ArrayList<Integer> getDiag(int pos)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (!isSouthEdge(pos))
        {
            int s = south(pos);
            if (!isWestEdge(s))
                res.add(west(s));
            if (!isEastEdge(s))
                res.add(east(s));
        }
        if (!isNorthEdge(pos))
        {
            int n = north(pos);
            if (!isWestEdge(n))
                res.add(west(n));
            if (!isEastEdge(n))
                res.add(east(n));
        }
        return res;
    }
    public ArrayList<Integer> getAround(int pos)
    {
        ArrayList<Integer> res = getDiag(pos);
        res.addAll(getAdjacent(pos));
        return res;
    }
    public ArrayList<Integer> getAround(int pos, int dis)
    {
        ArrayList<Integer> res = new ArrayList();
        int x = posX(pos);
        int y = posY(pos);
        for (int dx = -dis; dx <= dis; dx++)
            for (int dy = -dis; dy <= dis; dy++)
                if (!(dx == 0 && dy == 0) && Math.abs(dx) + Math.abs(dy) <= dis)
                {
                    if (inBoard(x + dx, y + dy))
                        res.add(makePos(x + dx, y + dy));
                }
        return res;
    }
    public ArrayList<Integer> getStars()
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int a = 3, b = BOARD_LENGTH - 4;
        res.add(makePos(a, a));
        res.add(makePos(a, b));
        res.add(makePos(b, a));
        res.add(makePos(b, b));
        return res;
    }
    public ArrayList<Integer> getAdjacent(int pos, PosSet ps)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int p : ps)
            if (isAdjacent(pos, p))
                res.add(p);
        return res;
    }
    public int getPosLib(int pos)
    {
        int res = 0;
        for (int i : getAdjacent(pos))
            if (board[i] == Color.EMPTY)
                res++;
        return res;
    }
    public Color[] getBoard()
    {
        return board.clone();
    }
    public boolean inBoard(int x, int y)
    {
        return (x >= 0 && x < BOARD_LENGTH && y >= 0 && y < BOARD_LENGTH);
    }
}
